/*
现在有一个 m * n 的整数矩阵，请你编写一个程序计算出一条从左到右穿过矩阵的路径，并使此路径的费用最小。路径从矩阵的左侧的第一列的任意单元格开始，逐步穿过矩阵到达最右侧的一列的任意单元格。每一步是指从某单元格进入它一列的相邻单元格（如下图，可以是横向或斜向）。矩阵的第一行和最后一行实际是相邻的，你可以想象矩阵是包裹在一个横放的圆柱体外面。


路径的花费是指这条路径所穿越的所有单元格中的数字之和。

穿越两个略有不同的 5 * 6 的矩阵的路径如下图所示，这两个矩阵只有最后一行的数字不同。右侧的路径显示了第一行和最后一行相邻的效果。

输入
输入包括一系列矩阵描述。每个矩阵描述的第一行是 m 和 n，即矩阵的行数和列数；之后的 m 行，每行包括 n 个以空格分开的整数，则是当前矩阵的值，注意矩阵的值未必是正数。

矩阵的行数 m 和列数 n 的范围是：1 <= m <= 10、 1 <= n <= 100；所有路径的费用值都可以用 30bit 的整数表示。

输出
针对每一个矩阵，找出费用最小的路径，并将其输出。每个矩阵的输出包括两行，第一行是路径本身，即输出每一步所在的行，第二行则是该路径的费用。

如果对于同一个矩阵有多条不同的费用最小路径，则输出左端行号较小的一条。

来源
UVa : 116
*/



#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#if defined(_WIN32) && !defined(__cplusplus)
#define inline __inline
#endif

#include <stdio.h>

#define M_MAX 10
#define N_MAX 100

#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define min(a,b)    (((a) < (b)) ? (a) : (b))

#define MinRow(a,b) ()

typedef struct
{
	int x;
	int y;
	int value;
}Point;


static inline Point GetMin(Point a, Point b)
{
	int flag = a.value - b.value;
	if (flag > 0)return b;
	else if (flag < 0)return a;
	else
	{
		return (((a.y) < (b.y)) ? (a) : (b));
	}
}


int main()
{
	int m, n;
	int dp[M_MAX][N_MAX];
	int path[M_MAX][N_MAX];

	while (scanf("%d%d", &m, &n) != EOF)
	{
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf("%d", &dp[i][j]);
			}
		}

		for (int j = n - 2; j >= 0; j--)
		{
			for (int i = m - 1; i >= 0; i--)
			{
				Point a = {j + 1,i,dp[i][j + 1]};
				Point b = {j + 1,(i + 1) % m,dp[(i + 1) % m][j + 1]};
				Point c = {j + 1,(i - 1 + m) % m,dp[(i - 1 + m) % m][j + 1]};
				Point min = GetMin(a, GetMin(b, c));


				dp[i][j] += dp[min.y][j + 1];
				path[i][j] = min.y;
			}
		}

		int rowStart = 0;
		for (int i = 0; i < m; i++)
		{
			rowStart = dp[i][0] < dp[rowStart][0] ? i : rowStart;
		}

		printf("%d", rowStart + 1);
		for (int j = 0, nextRow = rowStart; j < n - 1; j++)
		{
			printf(" %d", path[nextRow][j] + 1);
			nextRow = path[nextRow][j];
		}
		printf("\n%d\n", dp[rowStart][0]);
	}
}
